{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Binary Search Tree from Preorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #binary-search-tree #array #binary-tree #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #二叉搜索树 #数组 #二叉树 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bstFromPreorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #前序遍历构造二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组，它表示BST(即 <strong>二叉搜索树</strong> )的 <strong>先</strong><strong>序遍历</strong> ，构造树并返回其根。</p>\n",
    "\n",
    "<p><strong>保证</strong> 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。</p>\n",
    "\n",
    "<p><strong>二叉搜索树</strong> 是一棵二叉树，其中每个节点，&nbsp;<code>Node.left</code>&nbsp;的任何后代的值 <strong>严格小于</strong> <code>Node.val</code>&nbsp;,&nbsp;<code>Node.right</code>&nbsp;的任何后代的值 <strong>严格大于</strong> <code>Node.val</code>。</p>\n",
    "\n",
    "<p>二叉树的 <strong>前序遍历</strong> 首先显示节点的值，然后遍历<code>Node.left</code>，最后遍历<code>Node.right</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2019/03/06/1266.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>preorder = [8,5,1,7,10,12]\n",
    "<strong>输出：</strong>[8,5,10,1,7,null,12]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> preorder = [1,3]\n",
    "<strong>输出:</strong> [1,null,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= preorder.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= preorder[i]&nbsp;&lt;= 10^8</code></li>\n",
    "\t<li><code>preorder</code> 中的值 <strong>互不相同</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-binary-search-tree-from-preorder-traversal](https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-binary-search-tree-from-preorder-traversal](https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,5,1,7,10,12]', '[1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "\n",
    "        def make(arr):\n",
    "            if len(arr) == 0:\n",
    "                return None\n",
    "            \n",
    "            r = TreeNode(arr[0])\n",
    "            i = 1\n",
    "            while i < len(arr):\n",
    "                if arr[i] > arr[0]:\n",
    "                    break\n",
    "                i += 1\n",
    "            r.left = make(arr[1:i])\n",
    "            r.right = make(arr[i:])\n",
    "            return r\n",
    "        \n",
    "        return make(preorder)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import Optional\n",
    "\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode(preorder[0])\n",
    "        for i in range(1, len(preorder)):\n",
    "            self.addTreeNode(root, preorder[i])\n",
    "        return root\n",
    "\n",
    "    def addTreeNode(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return TreeNode(val)\n",
    "        if root.val > val:\n",
    "            root.left = self.addTreeNode(root.left, val)\n",
    "        else:\n",
    "            root.right = self.addTreeNode(root.right, val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            l, r = [], []\n",
    "            root = TreeNode(preorder.pop(0))\n",
    "            for i in preorder:\n",
    "                if i >= root.val:\n",
    "                    r.append(i)\n",
    "                else:\n",
    "                    l.append(i)\n",
    "            root.left = self.bstFromPreorder(l)\n",
    "            root.right = self.bstFromPreorder(r)\n",
    "            return root\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(low, high):\n",
    "            if self.index == n:\n",
    "                return None\n",
    "            cur = preorder[self.index]\n",
    "            if low > cur or cur > high:\n",
    "                return None\n",
    "\n",
    "            self.index += 1\n",
    "            node = TreeNode(cur)\n",
    "            node.left = dfs(low, cur)\n",
    "            node.right = dfs(cur, high)\n",
    "            return node\n",
    "\n",
    "        n = len(preorder)\n",
    "        self.index = 0\n",
    "        return dfs(0, 10 ** 9)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "#         def addNode(root, num):\n",
    "#             if not root:\n",
    "#                 return TreeNode(num)\n",
    "\n",
    "#             if num < root.val:\n",
    "#                 root.left = addNode(root.left, num)\n",
    "#             else:\n",
    "#                 root.right = addNode(root.right, num)\n",
    "#             return root\n",
    "\n",
    "#         root = None\n",
    "#         for i in range(len(preorder)):\n",
    "#             root = addNode(root, preorder[i])\n",
    "#         return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(preorder):\n",
    "            if len(preorder) == 1:\n",
    "                return TreeNode(preorder[0])\n",
    "            if preorder:\n",
    "                root = TreeNode(preorder[0])\n",
    "                value = preorder[0]\n",
    "                index = 0\n",
    "                for i in range(1,len(preorder)):\n",
    "                    if preorder[i] > value:\n",
    "                        index = i \n",
    "                        break\n",
    "                if index != 0:\n",
    "                    root.left = dfs(preorder[1:index])\n",
    "                    root.right = dfs(preorder[index:])\n",
    "                if index == 0:\n",
    "                    root.left = dfs(preorder[1:])\n",
    "                return root\n",
    "        return dfs(preorder)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            root = TreeNode(preorder[0])\n",
    "            devide = next((i for i, val in enumerate(preorder) if val > root.val), len(preorder))\n",
    "            root.left = self.bstFromPreorder(preorder[1: devide])\n",
    "            root.right = self.bstFromPreorder(preorder[devide: ])\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root = TreeNode(val = preorder[0])\n",
    "\n",
    "        n = len(preorder)\n",
    "        if n==1:\n",
    "            return root\n",
    "\n",
    "        i = 1\n",
    "        while i<n:\n",
    "            if preorder[i] > preorder[0]:\n",
    "                break\n",
    "            i += 1\n",
    "        \n",
    "        if i==n-1 and preorder[i] < preorder[0]:\n",
    "            root.left = self.bstFromPreorder(preorder[1:])\n",
    "        else:\n",
    "            root.left = self.bstFromPreorder(preorder[1:i])\n",
    "            root.right = self.bstFromPreorder(preorder[i:])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        self.head = None\n",
    "        inorder = sorted(preorder)\n",
    "\n",
    "        def buildBST(in_nums, pre_nums):\n",
    "            root_val = pre_nums[0]\n",
    "            in_root_pos = in_nums.index(root_val)\n",
    "\n",
    "            if in_root_pos == 0:\n",
    "                in_ind1 = in_ind2 = pre_ind1 = pre_ind2 = -1\n",
    "            else:\n",
    "                in_ind1, in_ind2 = 0, in_root_pos-1\n",
    "                pre_ind1, pre_ind2 = 1, in_root_pos\n",
    "            \n",
    "            if in_root_pos == len(in_nums)-1:\n",
    "                in_ind3 = in_ind4 = pre_ind3 = pre_ind4 = -1\n",
    "            else:\n",
    "                in_ind3 = pre_ind3 = in_root_pos + 1\n",
    "            \n",
    "            root = TreeNode(root_val)\n",
    "            if self.head is None: self.head = root\n",
    "            if in_ind1 == -1:\n",
    "                root.left = None\n",
    "            else:\n",
    "                root.left = buildBST(in_nums[in_ind1:in_ind2+1], pre_nums[pre_ind1:pre_ind2+1])\n",
    "            if in_ind3 == -1:\n",
    "                root.right = None\n",
    "            else:\n",
    "                root.right = buildBST(in_nums[in_ind3:], pre_nums[pre_ind3:])\n",
    "            return root\n",
    "        buildBST(inorder, preorder)\n",
    "        return self.head\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:\n",
    "        def dfs(left: int, right: int) -> TreeNode:\n",
    "            \"\"\"递归子区间，构造二叉搜索树\"\"\"\n",
    "\n",
    "            # 若区间为空，直接返回空节点\n",
    "            if left > right:\n",
    "                return None \n",
    "\n",
    "            # 当前节点的值为区间的第一个元素\n",
    "            node = TreeNode(preorder[left])\n",
    "\n",
    "            # 若区间只有1个元素，当前节点为叶节点，直接返回该节点\n",
    "            if left == right:\n",
    "                return node \n",
    "\n",
    "            # binary search find index of node value\n",
    "            idx = bisect.bisect_left(preorder[left+1: right+1], node.val) + left + 1\n",
    "            # l, r = left, right \n",
    "            # while l < r:\n",
    "            #     mid = l + (r - l + 1) // 2\n",
    "            #     if preorder[mid] < node.val:\n",
    "            #         l = mid # 下一轮搜索区间为[mid, r]\n",
    "            #     else:\n",
    "            #         r = mid-1  # 下一轮搜索区间为[l, mid-1]\n",
    "\n",
    "            node.left = dfs(left + 1, idx-1)\n",
    "            node.right = dfs(idx, right)\n",
    "            \n",
    "            return node\n",
    "\n",
    "\n",
    "        return dfs(0, len(preorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        n=len(preorder)\n",
    "        if n==0:return None\n",
    "        if n==1:return TreeNode(preorder[0])\n",
    "        j=n\n",
    "        for _ in range(1,n):\n",
    "            # if preorder[_]<preorder[0] and i!=0:i=_\n",
    "            if preorder[_]>preorder[0]:\n",
    "                j=_\n",
    "                break\n",
    "        # print(preorder[1:j])\n",
    "        # print(preorder[j:])\n",
    "        left=self.bstFromPreorder(preorder[1:j])\n",
    "        right=self.bstFromPreorder(preorder[j:])\n",
    "        return TreeNode(preorder[0],left,right)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.buildBST(preorder, 0, len(preorder)-1)\n",
    "\n",
    "    def buildBST(self, preorder, pStart, pEnd):\n",
    "        if pStart > pEnd:\n",
    "            return None\n",
    "        rootval = preorder[pStart]\n",
    "        root = TreeNode(rootval)\n",
    "        p = pStart+1\n",
    "        while p <= pEnd and preorder[p] < rootval:\n",
    "            p += 1\n",
    "        root.left = self.buildBST(preorder, pStart+1, p-1)\n",
    "        root.right = self.buildBST(preorder, p, pEnd)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def insertNode(root, val):\n",
    "            if val < root.val:\n",
    "                if root.left is None: \n",
    "                    root.left = TreeNode(val)\n",
    "                else:\n",
    "                    root.left = insertNode(root.left, val)\n",
    "            else:\n",
    "                if root.right is None: \n",
    "                    root.right = TreeNode(val)\n",
    "                else:\n",
    "                    root.right = insertNode(root.right,val)\n",
    "            return root\n",
    "        root = TreeNode(preorder[0])\n",
    "        for i in range(1, len(preorder)):\n",
    "            insertNode(root, preorder[i])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder == []:\n",
    "            return None\n",
    "        root_val = preorder[0]\n",
    "        left_lst = []\n",
    "        right_lst = []\n",
    "        for idx in range(1,len(preorder)):\n",
    "            if preorder[idx] < root_val:\n",
    "                left_lst.append(preorder[idx])\n",
    "            else:\n",
    "                right_lst.append(preorder[idx])\n",
    "        root = TreeNode(root_val)\n",
    "        root.left = self.bstFromPreorder(left_lst)\n",
    "        root.right = self.bstFromPreorder(right_lst)\n",
    "        return root\n",
    "        #print(root_val,left_lst,right_lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return\n",
    "        root = TreeNode(val = preorder[0])\n",
    "        preorderLeft = []\n",
    "        preorderRight = []\n",
    "        for oneNode in preorder[1:]:\n",
    "            if oneNode < preorder[0]:\n",
    "                preorderLeft.append(oneNode)\n",
    "            else:\n",
    "                preorderRight.append(oneNode)\n",
    "        root.left = self.bstFromPreorder(preorderLeft)\n",
    "        root.right = self.bstFromPreorder(preorderRight)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def check(nums):\n",
    "            for i in range(1, len(nums) - 1):\n",
    "                if nums[i] <= nums[0] <= nums[i + 1]:\n",
    "                    return i + 1\n",
    "            if nums[0] == min(nums):\n",
    "                return 1\n",
    "            if nums[0] == max(nums):\n",
    "                return len(nums)\n",
    "\n",
    "        def dfs(nums):\n",
    "            if not nums:\n",
    "                return None\n",
    "            root = TreeNode(nums[0])\n",
    "            i = check(nums)\n",
    "            left = dfs(nums[1: i])\n",
    "            right = dfs(nums[i:])\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            return root\n",
    "        return dfs(preorder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildtree(self, nums):\n",
    "        if len(nums) <= 0: return None\n",
    "        mid = 1\n",
    "        while len(nums) > mid and nums[mid] < nums[0]: mid += 1\n",
    "        root = TreeNode(nums[0])\n",
    "        # 搞定左子树 \n",
    "        root.left = self.buildtree(nums[1:mid])\n",
    "        root.right = self.buildtree(nums[mid:])\n",
    "        return root\n",
    "\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.buildtree(preorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        \n",
    "        def f(l, r):\n",
    "            if l > r:\n",
    "                return None \n",
    "            root = TreeNode(preorder[l])\n",
    "            if l == r :\n",
    "                return root\n",
    "\n",
    "            less = l\n",
    "            for i in range(l, r+1):\n",
    "                if preorder[i] <= preorder[l]:\n",
    "                    less = i \n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            root.left = f(l+1, less)\n",
    "            root.right = f(less+1, r)\n",
    "            return root \n",
    "        ans = f(0, len(preorder)-1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            root = TreeNode(preorder[0])\n",
    "            root.left = self.bstFromPreorder([n for n in preorder if n < preorder[0]])\n",
    "            root.right = self.bstFromPreorder([n for n in preorder if n > preorder[0]])\n",
    "            return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return \n",
    "        a=preorder[0]\n",
    "        root=TreeNode(a)\n",
    "        n=len(preorder)\n",
    "        l=1\n",
    "        while l<=n-1 and preorder[l]<=a:\n",
    "            l+=1\n",
    "        ll=self.bstFromPreorder(preorder[1:l])\n",
    "        rr=self.bstFromPreorder(preorder[l:])\n",
    "        root.left=ll\n",
    "        root.right=rr\n",
    "        return root\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root = TreeNode(val=preorder[0])\n",
    "        split_index = 1\n",
    "        for i in range(1, len(preorder)):\n",
    "            if preorder[0] > preorder[i]:\n",
    "                split_index += 1\n",
    "\n",
    "        root.left = self.bstFromPreorder(preorder[1: split_index])\n",
    "        root.right = self.bstFromPreorder(preorder[split_index:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def recur(lo: int, hi: int) -> TreeNode:\n",
    "            if hi < lo:\n",
    "                return None\n",
    "            root = TreeNode(preorder[lo])\n",
    "            pivot = lo + 1\n",
    "            while pivot <= hi and preorder[pivot] <= preorder[lo]:\n",
    "                pivot += 1\n",
    "            root.left = recur(lo+1, pivot-1)\n",
    "            root.right = recur(pivot, hi)\n",
    "            return root\n",
    "        return recur(0, len(preorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:\n",
    "        if preorder:\n",
    "            root = TreeNode(preorder[0])\n",
    "            devide = next((i for i, val in enumerate(preorder) if val > root.val), len(preorder))\n",
    "            root.left = self.bstFromPreorder(preorder[1: devide])\n",
    "            root.right = self.bstFromPreorder(preorder[devide: ])\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        #给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。\n",
    "        #二叉搜索树的中序是一个顺序序列，也就变成了我知道根结点知道中序，求前序序列\n",
    "        inorder = sorted(preorder) #获得中序排列 \n",
    "        def createTree(pOrder,iOrder):#给定中序和先序构造树\n",
    "            if len(pOrder) == 0 :return None\n",
    "            root = TreeNode(pOrder[0]) #获取该子树的根结点\n",
    "            rootIndex = iOrder.index(root.val) # 通过val获取中序遍历的序号\n",
    "            root.left = createTree(pOrder[1:rootIndex+1],iOrder[0:rootIndex])\n",
    "            root.right = createTree(pOrder[rootIndex+1:],iOrder[rootIndex+1:])\n",
    "            return root \n",
    "        return createTree(preorder,inorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "\n",
    "        left_list = []\n",
    "        right_list = []\n",
    "        \n",
    "        for i in range(1, len(preorder)):\n",
    "            if preorder[i] < preorder[0]:\n",
    "                left_list.append(preorder[i])\n",
    "            elif preorder[i] > preorder[0]:\n",
    "                right_list.append(preorder[i])\n",
    "        \n",
    "        root = TreeNode(preorder[0], left = self.bstFromPreorder(left_list), right = self.bstFromPreorder(right_list))\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        node = TreeNode(preorder[0])\n",
    "        node.left = self.bstFromPreorder([ i for i in preorder[1:] if i < preorder[0]])\n",
    "        node.right = self.bstFromPreorder([i for i in preorder[1:] if i > preorder[0]])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            root_val = preorder.pop(0)\n",
    "            root = TreeNode(root_val)\n",
    "            root.left = self.bstFromPreorder([i for i in preorder if i<root_val])\n",
    "            root.right = self.bstFromPreorder([i for i in preorder if i>root_val])\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def get_index(self, preorder):\n",
    "        for i in range(1, len(preorder)):\n",
    "            if preorder[i] > preorder[0]:\n",
    "                return i\n",
    "        return -1\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return node\n",
    "        index = self.get_index(preorder)\n",
    "        left = self.bstFromPreorder(preorder[1:]) if index == -1 else self.bstFromPreorder(preorder[1:index])\n",
    "        right = None if index == -1 else self.bstFromPreorder(preorder[index:])\n",
    "        node.left = left\n",
    "        node.right = right\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(order):\n",
    "            if not order:\n",
    "                return \n",
    "            if len(order) == 1:\n",
    "                return TreeNode(order[0])\n",
    "            a = order[0]\n",
    "            root = TreeNode(order[0])\n",
    "            l = order[1:]\n",
    "            b = bisect_left(l, a)\n",
    "            root.left = build(l[:b])\n",
    "            root.right = build(l[b:])\n",
    "            return root\n",
    "        return build(preorder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        leftList = []\n",
    "        rightList = []\n",
    "        root = TreeNode(preorder[0])\n",
    "        for num in preorder[1:]:\n",
    "            if num < preorder[0]:\n",
    "                leftList.append(num)\n",
    "            elif num > preorder[0]:\n",
    "                rightList.append(num)\n",
    "        root.left = self.bstFromPreorder(leftList)\n",
    "        root.right = self.bstFromPreorder(rightList)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not len(preorder):\n",
    "            return None\n",
    "        \n",
    "        cur_val = preorder[0]\n",
    "        left_tree = []\n",
    "        right_tree = []\n",
    "\n",
    "        for val in preorder[1:]:\n",
    "            if val<cur_val:\n",
    "                left_tree.append(val)\n",
    "            else:\n",
    "                right_tree.append(val)\n",
    "        \n",
    "        return TreeNode(val=cur_val, \n",
    "                        left=self.bstFromPreorder(left_tree),\n",
    "                        right=self.bstFromPreorder(right_tree)\n",
    "                        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        n=len(preorder)\n",
    "        if n==0:\n",
    "            return \n",
    "        if n==1:\n",
    "            return TreeNode(preorder[0])\n",
    "        idx=n\n",
    "        for i in range(n):\n",
    "            if preorder[i]>preorder[0]:\n",
    "                idx=i\n",
    "                break\n",
    "\n",
    "        return TreeNode(preorder[0],self.bstFromPreorder(preorder[1:idx]),self.bstFromPreorder(preorder[idx:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        n = len(preorder)\n",
    "\n",
    "        if n==0:\n",
    "            return None\n",
    "        if n==1:\n",
    "            return TreeNode(preorder[0],None,None)\n",
    "\n",
    "        root_val = preorder[0]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        right_index = n\n",
    "        for i in range(n):\n",
    "            if preorder[i]>root_val:\n",
    "                right_index = i\n",
    "                break\n",
    "                \n",
    "        root.left = self.bstFromPreorder(preorder[1:right_index])\n",
    "\n",
    "        root.right = self.bstFromPreorder(preorder[right_index:])\n",
    "\n",
    "        return root\n",
    "\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(pre):\n",
    "            if not pre:\n",
    "                return None\n",
    "            root = TreeNode(val = pre[0])\n",
    "\n",
    "            n = len(pre)\n",
    "            if n==1:\n",
    "                return root\n",
    "\n",
    "            i = 1\n",
    "            while i<n:\n",
    "                if pre[i] > pre[0]:\n",
    "                    break\n",
    "                i += 1\n",
    "            \n",
    "            if i==n-1 and pre[i] < pre[0]:\n",
    "                root.left = build(pre[1:])\n",
    "            else:\n",
    "                root.left = build(pre[1:i])\n",
    "                root.right = build(pre[i:])\n",
    "            return root\n",
    "\n",
    "        return build(preorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(L, R):\n",
    "            if L > R:\n",
    "                return None\n",
    "\n",
    "            root = TreeNode(val = preorder[L])\n",
    "            i = L+1\n",
    "            while i <= R and preorder[i] < preorder[L]:\n",
    "                i += 1\n",
    "            root.left = dfs(L+1, i-1)\n",
    "            root.right = dfs(i, R)\n",
    "            return root\n",
    "        return dfs(0, len(preorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(start,end):\n",
    "            if start > end :\n",
    "                return None\n",
    "            root = TreeNode(preorder[start])\n",
    "            index = start +1\n",
    "            while index <=end:\n",
    "                if preorder[index] > root.val:\n",
    "                    break\n",
    "                index +=1\n",
    "            root.left = dfs(start+1,index-1)\n",
    "            root.right = dfs(index,end)\n",
    "            return root\n",
    "        return dfs(0,len(preorder)-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        # 数组第一个值为根，将数组剩余部分划分为一大一小两个子数组，重复执行\n",
    "        if not preorder or len(preorder) == 0:\n",
    "            return \n",
    "        root = TreeNode(val = preorder[0])\n",
    "        leftList = []\n",
    "        rightList = []\n",
    "        for i in range(1, len(preorder)):\n",
    "            if preorder[i] > root.val:\n",
    "                leftList = preorder[1: i]\n",
    "                rightList = preorder[i: ]\n",
    "                break\n",
    "        if len(leftList) == 0 and len(rightList) == 0:\n",
    "            leftList = preorder[1: ]\n",
    "        root.left = self.bstFromPreorder(leftList)\n",
    "        root.right = self.bstFromPreorder(rightList)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def traverse(idx, order):\n",
    "            if idx >= len(order):\n",
    "                return None\n",
    "            r_idx = len(order)\n",
    "            for i, v in enumerate(order):\n",
    "                if v > order[idx]:\n",
    "                    r_idx = i\n",
    "                    break\n",
    "            return TreeNode(order[idx], traverse(0, order[1:r_idx]), traverse(0, order[r_idx:]))\n",
    "        return traverse(0, preorder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(left: int, right: int) -> Optional[TreeNode]:\n",
    "            if left > right:\n",
    "                return None\n",
    "            \n",
    "            root_idx = left\n",
    "            right_start = left+1\n",
    "            for i in range(left+1, right+1):\n",
    "                if preorder[i] > preorder[root_idx]:\n",
    "                    right_start = i\n",
    "                    break\n",
    "                if preorder[right] < preorder[root_idx]:\n",
    "                    right_start += 1\n",
    "\n",
    "            return TreeNode(preorder[root_idx], dfs(left+1, right_start-1), dfs(right_start, right))\n",
    "        \n",
    "        return dfs(0, len(preorder) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.build(preorder, 0, len(preorder)-1)\n",
    "\n",
    "    def build(self, preorder, start, end):\n",
    "        if start > end:\n",
    "            return None\n",
    "        rootval = preorder[start]\n",
    "        root = TreeNode(rootval)\n",
    "        p = start + 1\n",
    "        while p <= end and preorder[p] < rootval:\n",
    "            p += 1\n",
    "        root.left = self.build(preorder, start+1, p-1)\n",
    "        root.right = self.build(preorder, p, end)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(i: int, j: int) -> Optional[TreeNode]:\n",
    "            if i >= j:\n",
    "                return None\n",
    "            root = TreeNode(preorder[i])\n",
    "            k = i + 1\n",
    "            while k < j and preorder[k] < preorder[i]:\n",
    "                k += 1\n",
    "            root.left = dfs(i + 1, k)\n",
    "            root.right = dfs(k, j)\n",
    "            return root\n",
    "        return dfs(0, len(preorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def solve(l, r):\n",
    "            if l == r:\n",
    "                return TreeNode(preorder[l])\n",
    "            elif l > r:\n",
    "                return None\n",
    "            \n",
    "            mid, lb = preorder[l], l + 1\n",
    "            while lb <= r and preorder[lb] < mid:\n",
    "                lb += 1\n",
    "            \n",
    "            # print(l, r, mid, lb)\n",
    "            return TreeNode(mid, solve(l + 1, lb - 1), solve(lb, r))\n",
    "        \n",
    "        return solve(0, len(preorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            root=TreeNode(preorder[0])\n",
    "            devide=next((i for i,val in enumerate(preorder) if val>root.val),len(preorder))\n",
    "            root.left=self.bstFromPreorder(preorder[1:devide])\n",
    "            root.right=self.bstFromPreorder(preorder[devide:])\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            root = TreeNode(preorder[0])\n",
    "            devide = next((i for i, val in enumerate(preorder) if val > root.val), len(preorder))\n",
    "            root.left = self.bstFromPreorder(preorder[1: devide])\n",
    "            root.right = self.bstFromPreorder(preorder[devide: ])\n",
    "            return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            root = TreeNode(preorder[0])\n",
    "            devide = next((i for i, val in enumerate(preorder) if val > root.val), len(preorder))\n",
    "            root.left = self.bstFromPreorder(preorder[1: devide])\n",
    "            root.right = self.bstFromPreorder(preorder[devide: ])\n",
    "            return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:return None\n",
    "\n",
    "        rootval=preorder[0]\n",
    "        pivot=len(preorder)\n",
    "\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i]>rootval:\n",
    "                pivot=i\n",
    "                break\n",
    "\n",
    "        root=TreeNode(rootval)\n",
    "        root.left=self.bstFromPreorder(preorder[1:pivot])\n",
    "        root.right=self.bstFromPreorder(preorder[pivot:])\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        res = self.build(preorder, -inf, inf)\n",
    "        return res \n",
    "\n",
    "    def build(self, arr, low, high):\n",
    "\n",
    "        if not arr or arr[0] < low or arr[0] > high:\n",
    "            return\n",
    "        \n",
    "        value = arr.pop(0)\n",
    "        root = TreeNode(value)\n",
    "\n",
    "        root.left = self.build(arr, low, value)\n",
    "        root.right = self.build(arr, value, high)\n",
    "\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = None\n",
    "        for a in preorder:\n",
    "            root = self.build(root, a)\n",
    "        return root\n",
    "\n",
    "    def build(self, root, val):\n",
    "        if root is None:\n",
    "            return TreeNode(val)\n",
    "        if root.val > val:\n",
    "            root.left = self.build(root.left, val)\n",
    "        else:\n",
    "            root.right = self.build(root.right, val)\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        \n",
    "        def f(l, r):\n",
    "            if l > r:\n",
    "                return None \n",
    "            root = TreeNode(preorder[l])\n",
    "            if l == r :\n",
    "                return root\n",
    "\n",
    "            less = l\n",
    "            for i in range(l, r+1):\n",
    "                if preorder[i] <= preorder[l]:\n",
    "                    less = i \n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            root.left = f(l+1, less)\n",
    "            root.right = f(less+1, r)\n",
    "            return root \n",
    "        ans = f(0, len(preorder)-1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            root = TreeNode(preorder[0])\n",
    "            devide = next((i for i, val in enumerate(preorder) if val > root.val), len(preorder))\n",
    "            root.left = self.bstFromPreorder(preorder[1:devide])\n",
    "            root.right = self.bstFromPreorder(preorder[devide:])\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        t = preorder[0]\n",
    "        ans = TreeNode(t)\n",
    "        a = preorder[1:]\n",
    "        i = bisect_left(a, t)\n",
    "        ans.left = self.bstFromPreorder(a[:i])\n",
    "        ans.right = self.bstFromPreorder(a[i:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        inorder = sorted(preorder)\n",
    "        def buildTree(preorder, inorder):\n",
    "            if preorder:\n",
    "                root = TreeNode(preorder[0])\n",
    "                i = inorder.index(preorder[0])\n",
    "                root.left = buildTree(preorder[1:i+1], inorder[:i])\n",
    "                root.right = buildTree(preorder[i+1:], inorder[i+1:])\n",
    "                return root\n",
    "            return\n",
    "\n",
    "        return buildTree(preorder, inorder)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(qian):\n",
    "            # print(qian)\n",
    "            if qian==[]:return None\n",
    "            mid=qian[0]\n",
    "            dx=len(qian)\n",
    "            for i in range(len(qian)):\n",
    "                if qian[i]>mid:\n",
    "                    dx=i\n",
    "                    break\n",
    "            leftqian = qian[1:dx]\n",
    "            rightqian=qian[dx:]\n",
    "            midNode=TreeNode(mid)\n",
    "            midNode.left=build(leftqian)\n",
    "            midNode.right=build(rightqian)\n",
    "            return midNode\n",
    "        return build(preorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def get_index(self, preorder):\n",
    "        for i in range(1, len(preorder)):\n",
    "            if preorder[i] > preorder[0]:\n",
    "                return i\n",
    "        return -1\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return node\n",
    "        index = self.get_index(preorder)\n",
    "        if index == -1:\n",
    "            left = self.bstFromPreorder(preorder[1:])\n",
    "            right = None\n",
    "        else:\n",
    "            left = self.bstFromPreorder(preorder[1:index])\n",
    "            right = self.bstFromPreorder(preorder[index:])\n",
    "        node.left = left\n",
    "        node.right = right\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(nums):\n",
    "            if not nums:\n",
    "                return\n",
    "            node_val = nums[0]\n",
    "            root = TreeNode(node_val)\n",
    "            i = 1\n",
    "            while i < len(nums) and nums[i] < node_val:\n",
    "                i += 1\n",
    "            root.left = dfs(nums[1:i])\n",
    "            root.right = dfs(nums[i:])\n",
    "            return root\n",
    "        return dfs(preorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = None\n",
    "        for a in preorder:\n",
    "            root = self.build(root, a)\n",
    "        return root\n",
    "\n",
    "    def build(self, root, val):\n",
    "        if root is None:\n",
    "            return TreeNode(val)\n",
    "        if root.val > val:\n",
    "            root.left = self.build(root.left, val)\n",
    "        else:\n",
    "            root.right = self.build(root.right, val)\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not len(preorder):\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        partition = len(preorder)\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] > root.val:\n",
    "                partition = i\n",
    "                break\n",
    "        root.left = self.bstFromPreorder(preorder[1:partition])\n",
    "        root.right = self.bstFromPreorder(preorder[partition:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:return \n",
    "        \n",
    "        rootVal=preorder[0]\n",
    "        pivot=len(preorder)\n",
    "        \n",
    "        for i in range(1,len(preorder)):\n",
    "            if preorder[i]>rootVal:\n",
    "                pivot = i\n",
    "                break\n",
    "                \n",
    "\n",
    "        root=TreeNode(rootVal)\n",
    "        root.left=self.bstFromPreorder(preorder[1:pivot])\n",
    "        root.right=self.bstFromPreorder(preorder[pivot:])\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:return \n",
    "        print(preorder)\n",
    "        \n",
    "        rootVal=preorder[0]\n",
    "        pivot=len(preorder)\n",
    "        \n",
    "        for i in range(1,len(preorder)):\n",
    "            if preorder[i]>rootVal:\n",
    "                pivot = i\n",
    "                break\n",
    "                \n",
    "\n",
    "        root=TreeNode(rootVal)\n",
    "        root.left=self.bstFromPreorder(preorder[1:pivot])\n",
    "        root.right=self.bstFromPreorder(preorder[pivot:])\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def buildTree(preorder: List[int]) -> Optional[TreeNode]:\n",
    "            if not preorder: return\n",
    "            root = TreeNode(val = preorder[0])\n",
    "            preorderLeft = []\n",
    "            preorderRight = []\n",
    "            for oneNode in preorder[1:]:\n",
    "                if oneNode < preorder[0]:\n",
    "                    preorderLeft.append(oneNode)\n",
    "                else:\n",
    "                    preorderRight.append(oneNode)\n",
    "            root.left = buildTree(preorderLeft)\n",
    "            root.right = buildTree(preorderRight)\n",
    "            return root\n",
    "        return buildTree(preorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def g(p):\n",
    "           if len(p)==0:\n",
    "              return  None\n",
    "           l=[x for x in p if x<p[0]]\n",
    "           r=[x for x in p if x>p[0]]\n",
    "           s=TreeNode(p[0])\n",
    "           s.left=g(l)\n",
    "           s.right=g(r)\n",
    "           return s\n",
    "        return g(preorder)   \n",
    "           \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def recur(lower,upper):#preorder数组对递归函数而言一直是个全局变量\n",
    "            \n",
    "            if len(preorder)==0:\n",
    "                return None\n",
    "            \n",
    "            if preorder[0]<lower or preorder[0]>upper:\n",
    "                return None\n",
    "            cur=preorder.pop(0)\n",
    "            root=TreeNode(cur)\n",
    "       \n",
    "            \n",
    "            root.left=recur(lower,cur)\n",
    "            root.right=recur(cur,upper)\n",
    "\n",
    "            \n",
    "            \n",
    "            return root\n",
    "        \n",
    "        return recur(-inf,inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:return None\n",
    "        root_val=preorder[0]\n",
    "        root=TreeNode(root_val)\n",
    "        idx=1\n",
    "        while idx<len(preorder) and preorder[idx]<root_val:\n",
    "            idx+=1\n",
    "        root.left=self.bstFromPreorder(preorder[1:idx])\n",
    "        root.right=self.bstFromPreorder(preorder[idx:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if preorder:\n",
    "            p, root = [[], []], TreeNode(preorder.pop(0))\n",
    "            for val in preorder:\n",
    "                if val < root.val:\n",
    "                    p[0].append(val)\n",
    "                else:\n",
    "                    p[1].append(val)\n",
    "            root.left = self.bstFromPreorder(p[0])\n",
    "            root.right = self.bstFromPreorder(p[1])\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return\n",
    "        length = len(preorder)\n",
    "        root_val = preorder[0]\n",
    "        root = TreeNode(root_val)\n",
    "        index = 0\n",
    "        while index < length:\n",
    "            if preorder[index] <= root_val:\n",
    "                index += 1\n",
    "            else:\n",
    "                break\n",
    "        first_larger = index\n",
    "        root.left = self.bstFromPreorder(preorder[1:first_larger])\n",
    "        root.right = self.bstFromPreorder(preorder[first_larger:])\n",
    "        return root\n",
    "\n",
    "\n",
    "    \n",
    "    # def get_first_larger(self, nums, target):\n",
    "    #     pass\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        # # 1. 二叉搜索树的中序遍历是递增的\n",
    "        # inorder = sorted(preorder)\n",
    "        # def buildTree(preorder, inorder):\n",
    "        #     if preorder:\n",
    "        #         root = TreeNode(preorder[0])\n",
    "        #         i = inorder.index(preorder[0])\n",
    "        #         root.left = buildTree(preorder[1:i+1], inorder[:i])\n",
    "        #         root.right = buildTree(preorder[i+1:], inorder[i+1:])\n",
    "        #         return root\n",
    "        #     return\n",
    "        # return buildTree(preorder, inorder)\n",
    "        # 2.小于根节点的都是左子树\n",
    "        def buildTree(preorder, start, end):\n",
    "            if start==end:return None\n",
    "            root = TreeNode(preorder[start])\n",
    "            leftEnd = start+1\n",
    "            while leftEnd<end and preorder[leftEnd]<preorder[start]:\n",
    "                leftEnd+=1\n",
    "            root.left = buildTree(preorder, start+1, leftEnd)\n",
    "            root.right = buildTree(preorder, leftEnd, end)\n",
    "            return root\n",
    "        return buildTree(preorder, 0, len(preorder))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        # 单调栈 找下一个更大值\n",
    "        n = len(preorder)\n",
    "        stack = []\n",
    "        mask = [-1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and preorder[stack[-1]] < preorder[i]:\n",
    "                mask[stack[-1]] = i\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        \n",
    "        print(mask)\n",
    "        \n",
    "        def build_tree(be, en):\n",
    "            if en == -1:\n",
    "                en = n\n",
    "            if be == en or be == -1:\n",
    "                return None\n",
    "            print(be, en)\n",
    "            node = TreeNode(val = preorder[be])\n",
    "            node.left = build_tree(be + 1, mask[be])\n",
    "            node.right = build_tree(mask[be], en)\n",
    "            return node\n",
    "        \n",
    "        return build_tree(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.reslist=[]\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(preorder,l1,r1):\n",
    "            if(l1>r1):\n",
    "                return None\n",
    "            rootval=preorder[l1]\n",
    "            root=TreeNode(rootval)\n",
    "            index=l1+1\n",
    "            while(index<=r1 and preorder[index]<rootval):\n",
    "                index+=1\n",
    "            print(preorder[l1:r1+1],preorder[l1+1:index])\n",
    "            left=build(preorder,l1+1,index-1)\n",
    "            right=build(preorder,index,r1)\n",
    "            root.left=left\n",
    "            root.right=right\n",
    "            return root\n",
    "        return build(preorder,0,len(preorder)-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        inorder=sorted(preorder)\n",
    "        dic_inorder={}\n",
    "        for i in range(len(inorder)):\n",
    "            dic_inorder[inorder[i]]=i\n",
    "\n",
    "        def dfs(node,pl,pr,il,ir):\n",
    "            #print(pl,pr,il,ir)\n",
    "            root=preorder[pl]\n",
    "            node.val=root\n",
    "\n",
    "            root_index=dic_inorder[root]\n",
    "            l_len=root_index-il\n",
    "            r_len=ir-root_index\n",
    "            \n",
    "            if pl+l_len>=pl+1:\n",
    "                node.left=dfs(TreeNode(),pl+1,pl+l_len,il,root_index-1)\n",
    "            if pr>=pl+l_len+1:\n",
    "                node.right=dfs(TreeNode(),pl+l_len+1,pr,root_index+1,ir)\n",
    "            return node\n",
    "        root=TreeNode()\n",
    "        dfs(root,0,len(inorder)-1,0,len(inorder)-1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "\n",
    "        node = TreeNode(preorder[0])\n",
    "        node.left = self.bstFromPreorder([i for i in preorder[1:] if i < preorder[0]])\n",
    "        node.right = self.bstFromPreorder([i for i in preorder[1:] if i > preorder[0]])\n",
    "        return node"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
